/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  let template = ['()', '[]', '{}']
  let stack = []
  for (let i = 0; i < s.length; i++) {
    let str = stack[stack.length - 1] + s[i]
    if (template.includes(str)) {
      stack.pop()
    } else {
      stack.push(s[i])
    }
  }

  return stack.length === 0
};